import random
import time
from fractions import gcd
#The Miller Rabin primality test is used to find the known primes for the RSA Based Primality Test
def miller_rabin(n):
          k = 10
          if n == 2:
                    return True
          if n % 2 == 0:
                    return False
          r, s = 0, n - 1
          while s % 2 == 0:
                    r += 1
                    s //= 2
          for _ in range(k):
                    a = random.randint(2, n - 1)
                    x = pow(a, s, n)
                    if x == 1 or x == n - 1:
                              continue
                    for _ in range(r - 1):
                              x = pow(x, 2, n)
                              if x == n - 1:
                                        break
                    else:
                              return False
          return True
def egcd(a,b):
          u, u1 = 1, 0
          v, v1 = 0, 1
          while b:
                    q = a // b
                    u, u1 = u1, u - q * u1
                    v, v1 = v1, v - q * v1
                    a, b = b, a - q * b
          return u
def mod_inverse(e,phi):
          return egcd(e,phi)%phi
def coprime_message(n):
          c = 1
          while c < n-1:
                    c += 1
                    m = random.randint(2, n-1)
                    if gcd(m, n) == 1:
                              return m
def primegen(n):
    c = 0
    int = 1
    out = []
    while c < n:
        int += 1
        if miller_rabin(int) == True:
            c += 1
            out.append(int)
    return out
def rsabpt(q, max):
#RSA Based Primality Test Function
#q is the given integer being tested for primality
#max is the number of known primes used in the function
    true_primes = primegen(max)
    for prime in true_primes:
        for e in true_primes:
          n = q*prime
          phi = (q-1)*(prime-1)
          d = mod_inverse(e, phi)
          if e < phi:
            if gcd(e, n) == 1:
              if gcd(e, phi) == 1:
                if gcd(d, n) == 1:
                  if gcd(d, phi) == 1:
                      if gcd(n, phi) == 1:
                            m = coprime_message(n)
                            c = pow(m, e, n)
                            m1 = pow(c, d, n)
                            if m1 != m:
                              return False
    return True
start = time.clock()
p, t = rsabpt(65537, 20), time.clock() - start
print(p, t)
#Test example, 65537 is a fermat prime
#Also showing the time.clock() function for determining CPU seconds used